//
// Created by liushuai on 12/21/19.
//
#include "climbStairs3.h"
std::vector<int> cache(2);
int climbStairs3(int n){
    if(n == 1)
        return 1;
    else if(n == 2)
        return 2;
    else{
        cache.at(0) = climbStairs3(n-2);
        cache.at(1) = climbStairs3(n-1)+climbStairs3(n-2);
        return cache.at(1);



    }
}
